Package edu.claflin.finder.algo.clustering

Class Walktrap

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.clustering.ClusteringAlgorithm

edu.claflin.finder.algo.clustering.Walktrap

All Implemented Interfaces:

Processable<Graph,Graph>

public class Walktrap
extends ClusteringAlgorithm

Community detection with the Walktrap Algorithm. Random walks from a Node in a community tend to stay in the same Node.

Author:

Cesar Martin and Adolfo Perera

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	Walktrap.MutualConnectionsRecord	Stores the delta sigmas between a Community C connected to community 1 or community 2.

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields

Modifier and Type	Field	Description
private java.util.HashMap<Node,java.lang.Integer>	degrees
private java.util.HashMap<java.lang.Integer,java.util.List<Node>>	list
private java.util.HashMap<java.lang.Integer,java.util.HashMap<Node,java.lang.Double>>	Pv
private int	steps
private boolean	weighted

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
Walktrap(ArgumentsBundle args)

Method Summary

Modifier and Type	Method	Description
private java.util.HashMap<Node,java.lang.Double>	cprobs(java.util.List<Node> C, Graph graph, java.util.List<Node> graphNodes)	Get a probability vector for a community.
private double	delta_sigma(int C1index, int C2index, java.util.List<Node> graphNodes)	Calculate delta sigma from communities C1 and C2 according to Section 4.2 Theorem 5 in the paper.
private double	distance(int i, int j, java.util.List<Node> graphNodes)	Compute the distance between community i and community j.
private java.util.HashMap<Node,java.lang.Double>	merge_probs(int i, int j)	Calculate the probability vectors of joining 2 communities.
java.util.ArrayList<Graph>	process(Graph graph)	Processes data.
private void	remove_node(HeapNodeWT info, java.util.PriorityQueue<HeapNodeWT> q)	Remove a HeapNode from the Queue.

Methods inherited from class edu.claflin.finder.algo.clustering.ClusteringAlgorithm

buildCommunityGraphs

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getPartiteNumber, removePropertyChangeListener, setGraphSortOrder, setPartiteNumber, setProgress

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

steps

private int steps

weighted

private boolean weighted

list

private java.util.HashMap<java.lang.Integer,java.util.List<Node>> list

degrees

private java.util.HashMap<Node,java.lang.Integer> degrees

Pv

private java.util.HashMap<java.lang.Integer,java.util.HashMap<Node,java.lang.Double>> Pv

Constructor Detail

Walktrap

public Walktrap(ArgumentsBundle args)

Method Detail

process

public java.util.ArrayList<Graph> process(Graph graph)

Description copied from interface: Processable

Processes data.

Parameters:

graph - the T type object to process.

Returns:

the S type object array produced by the processing.

remove_node

private void remove_node(HeapNodeWT info,
                         java.util.PriorityQueue<HeapNodeWT> q)

Remove a HeapNode from the Queue.

Parameters:

info - the node to remove

q - the priority queue to remove from

delta_sigma

private double delta_sigma(int C1index,
                           int C2index,
                           java.util.List<Node> graphNodes)

Calculate delta sigma from communities C1 and C2 according to Section 4.2 Theorem 5 in the paper.

Parameters:

C1index - the index of community C1 in the list

C2index - the index of community C2 in the list

graphNodes - the sorted Node list

Returns:

the delta sigma between C1 and C2

cprobs

private java.util.HashMap<Node,java.lang.Double> cprobs(java.util.List<Node> C,
                                                              Graph graph,
                                                              java.util.List<Node> graphNodes)

Get a probability vector for a community. The probabilities are of going from the community to all Nodes in a random walk of length steps instance variable. This is an adaptation of the int constructor of the Probabilities class in igraph master's walktrap_communities.cpp

Parameters:

C - the community

graph - the original graph

graphNodes - the sorted list of Nodes

Returns:

merge_probs

private java.util.HashMap<Node,java.lang.Double> merge_probs(int i,
                                                                   int j)

Calculate the probability vectors of joining 2 communities. Equation in section 4.4 of the paper (first bullet point). This is an adaptation of the 2 ints constructor of the Probabilities class in igraph master's walktrap_communities.cpp

Parameters:

i - index of community 1

j - index of community 2

Returns:

the new probability vector

distance

private double distance(int i,
                        int j,
                        java.util.List<Node> graphNodes)

Compute the distance between community i and community j. This is an adaptation of the 2 ints constructor of the compute_distance of the Probabilities class in igraph master's walktrap_communities.cpp

Parameters:

i - index of community 1

j - index of community 2

graphNodes - the sorted list of nodes

Returns:

the distance between the communities